The combinations of n objects taken k at a time
are the possible choice of k different elements from a collection of n objects.
The combinations of the five objects BLAH, taken three at a time, are
DISPLAY.
It is a simple matter to count the total number of k-combinations of n objects:
Equation (2) of the previous section told us that there are BLAH
ways to choose the first k objects for a permutation; and every k-combination
appears exactly k! times in these arrangements, since each combination appears
in all its permutations.  Therefore the number of combinations, which we denote by
BLAH, is
DISPLAY.
For example,
DISPLAY,
which is the number of combinations we found in (1).

The quantity BLAH is called a binomial coefficient; these numbers
have an extraordinary number of applications.  They are probably the most important
quantities entering into the analysis of algorithms, and so the reader is urged to
become familiar with them.

Equation (2) may be used to define BLAH even when n is not an integer.
We will now define the symbol BLAH for all real numbers r and all
integers k:
DISPLAY.
For particular cases we have
DISPLAY.
Table 1 gives values of the binomial coefficients for small integer values of
r and k. The values for BLAH should be memorized.

The binomial coefficients have a long and interesting history.  Table 1 is 
called ``Pascal's triangle'' because it appeared in Blaise Pascal's 
Traite du triangle arithmetique in 1653.  This treatise was significant
because it was one of the first works on probability theory, but Pascal did not
invent the binomial coefficients (which were well-known in Europe at that time).
Table 1 also appears in the treatise Szu-yuan Yu-chien (``The Precious
Mirror of the Four Elements'') by the Chinese mathematician Chu Shih-Chieh in
1303, where they are said to be an old invention.  The earliest known appearance
of binomial coefficients is in a tenth century commentary, due to
Halayudlha, on an ancient Hindu classic, the Chandah-Sutra.  In about 1150
the Hindu mathematician Bhascara Acharya gave a very clear exposition of
binomial coefficients in his book Lilavati, Section 6, Chapter 4.
For small values of k they were known much earlier; they appeared in Greek
and Roman writings with a geometric interpretation (cf. Fig. 8).  The
notation BLAH was introduced by Andreas von Ettingshausen in his
book Die Combinatorische Analysis (Vienna, 1826).

The reader has probably noticed several interesting patterns which appear
in Table 1.  Binomial coefficients satisfy literally thousands of identities,
and for centuries their amazing properties have been continually explored.
In fact, there are so many relations present that when someone finds a new
identity, there aren't many people who get excited about it any more, except
the discoverer!  In order to manipulate the formulas which arise in the
analysis of algorithms, a facility for handling binomial coefficients is a must,
and so an attempt has been made in this section to explain in a simple way how
to maneuver with these numbers.  Mark Twain once tried to reduce all jokes to a
dozen or so primitive kinds (e.g., farmer's daughter, mother-in-law, etc.);
we will try to condense the thousands to identities into a small set of basic
operations with which we can solve nearly every problem involving these numbers
that confronts us.

In most applications, both the numbers r and k which appear in 
BLAH will be integers.  Some of the techniques we will describe are
applicable only when both r and k are integers; so we will be careful
to list, at the right of each numbered equation, any restrictions on the variables
which appear.  For example, in Eq. (3) we have mentioned the requirement that
k is an integer; there is no restriction on r.

Now let us study the basic techniques for operating on binomial coefficients:

From Eq. (3)
we have immediately
DISPLAY.
This allows combinations of factorials to be represented as binomial coefficients
and conversely.

From Eqs. (3) and (5), we have
DISPLAY.
This formula holds for all integers k.  When k is negative or
greater than n, the binomial coefficient is zero (provided that n
is a nonnegative integer).

From the
definition (3), we have
DISPLAY.
This formula is very useful for combining a binomial coefficient with other parts
of an expression.  By elementary transformation we have the rules
DISPLAY,
the first of which is valid for all integers k, and the second is valid when no
division by zero has been performed.  We also have a similar relation:
DISPLAY.

Let us illustrate these transformations, by proving Eq. (8) using Eqs. (6) and
(7) alternately:
DISPLAY.
[Note: This derivation is valid only when r is a positive integer BLAH,
because of the constraints involved in Eqs. (6) and (7); yet Eq. (8) claims
to be valid for arbitrary BLAH.  This can be proved in a simple and
important manner: we have verified that
DISPLAY,
for infinitely many values of r.  Both sides of this equation are
polynomials in r.  A nonzero polynomial of degree n can have at most
n distinct zeros; so (by subtraction) if two polynomials of degree
BLAH agree at BLAH or more different points, the polynomials are
identically equal.  This principle may be used to extend the validity of many
identities from integers to all real numbers.]

The basic relation
DISPLAY,
is clearly valid in Table 1 (every value is the sum of the two values above and
to the left) and we may easily verify it in general from Eq. (3). Alternatively,
we have by Eqs. (7) and (8),
DISPLAY.
Equation (9) is often useful in obtaining proofs by induction on r, when r
is an integer.

Applying Eq. (9) repeatedly, we 
obtain two important summation formulas:
DISPLAY.

Equation (11) can easily be proved by induction on n, but it is interesting
to see how it can also be derived from Eq. (10) with two applications of
Eq. (6):

Equation (11) occurs very frequently in applications; in fact, we have already
derived special cases of it in previous sections.  For example, when BLAH, we
have 
DISPLAY,
our old friend, the sum of an arithmetic progression.

Suppose that we want the sum BLAH.  This can be solved by
observing that BLAH; hence
DISPLAY.
If desired, this answer, obtained in terms of binomial coefficients, can be put
back into polynomial notation:
DISPLAY.

The sum BLAH can be obtained in a similar way; any
polynomial BLAH can be expressed as
BLAH for suitably chosen
coefficients BLAH.  We will return to this subject later.

Of course, the binomial theorem
is one of our principal tools:
DISPLAY.
(At last we are able to justify the name ``binomial coefficient'' for our
numbers.)

It is important to note that we have written ``BLAH'' in Eq. (13), rather
than ``BLAH'' as might have been written. If no restriction is placed
on k, we are summing over all integers, BLAH; but the two notations
are exactly equivalent in this case, since when BLAH or BLAH, the terms in
Eq. (13) are all zero.  The simpler form ``BLAH'' is to be preferred, since
all manipulations with sums are simpler when the conditions of summation are
simpler.  We save a good deal of tedious effort if we do not need to keep track
of the lower and/or upper limits of summation, so the limits should be left as
infinity whenever possible.  Our notation has another advantage also:  If r
is not a nonnegative integer, Eq. (13) becomes an infinite sum, and
the binomial theorem of calculus states that Eq. (13) is valid
for all r, if BLAH.

It should be noted that formula (13) gives
DISPLAY,
and we will use this convention consistently.

The special case BLAH in Eq. (13) is so important we state is specially:
DISPLAY.

The discovery of the binomial theorem was announced by Isaac Newton in a letter
to Oldenburg on June 13, 1676.  He apparently had no real proof of the formula
(and at that time the necessity for rigorous proof was not fully realized).
The first attempted proof was given by L. Euler in 1774, although that also
was lacking in rigor; finally, K. F. Gauss gave the first actual proof in
1812.  In fact, Gauss's work represented the first time anything about
infinite sums was proved satisfactorily.

In the early nineteenth century, N. Abel found a surprising generalization
of the binomial formula (Eq. 13):
DISPLAY,
which is an identity in three variables, x, y, and z (cf. exercises
50 through 52).  Abel published and proved this formula in Volume 1 of the
German Journal fur die reine und angewandte Mathematik (1826),
pp. 159--160.  It is interesting to note that Abel contributed many other
papers to the same Volume 1, including his famous memoirs on the unsolvability
of algebraic equations of degree 5 or more, and on the binomial theorem. See
AMM 69 (1962), 572 for a number of references to Eq. (16).


The basic identity
DISPLAY
follows immediately from the definition (Eq. 3) when each term of the 
numerator is negated.  This is often a useful transformation on the upper index.

We will give one example of the use of Eq. (17) here to prove the summation
formula
DISPLAY.
This identity could be proved by induction using Eq. (9), but we can easily
use Eqs. (17) and (10):
DISPLAY.

An important application of Eq. (17) can be made when r is an integer:
DISPLAY.
[Take BLAH, BLAH in Eq. (17).] We have moved n from the upper
position to the lower.

When products of binomial
coefficients appear, there are usually several different ways to reexpress the
products by expanding into factorials and out again using Eq. (5).  For example,
DISPLAY.
It suffices to prove Eq. (20) when r is an integer BLah [cf. the remarks after
Eq. (8)], and when BLAH.  Then
DISPLAY.
Equation (20) is very useful when an index (namely m) appears in both the
upper and the lower position, and we wish to have it appear in one place rather
than two.  Note that Eq. (7) is the special case of Eq. (20) when BLAH.

To complete our set of
binomial-coefficient manipulations, we present the following very general
identities, which are proved in the exercises at the end of this section.  These
formulas show how to sum over a product of two binomial coefficients, considering
various places where the running variable k might appear:
DISPLAY.
Of these identities, Eq. (21) is by far the most important, and it should be
memorized.  One way to remember it is to interpret the righthand side as the number
of ways to select n people from among r men and s women; each term on the
left is the number of ways to choose k of the men and BLAH of the women.
Equation (21) is commonly called Vandermonde's convolution, since A. Vandermonde
published it in Mem. Acad. Roy. Sci. Paris (1772), 489--498.
However, it had appeared already in Chu Shih-Chieh's 1303 treatise mentioned
earlier [see J. Needham, Science and Civilization in China 3 (1959),
138--139].

If BLAH in Eq. (26), we avoid the zero denominator by cancelling with a 
factor in the numerator; in this way Eq. (21) is a polynomial identity in the
variables r, s, t.  Obviously Eq. (21) is a special case of Eq. (26)
with BLAH.  These formulas are the principal tools we have for working with
difficult sums.

We should point out a nonobvious use of Eqs. (23) and (25); it is often
helpful to replace the simple binomial coefficient on the righthand side by the
more complicated expression on the left, interchange the order of summation,
and simplify.  We may regard the left-hand sides as expansions of
DISPLAY.
Formula (23) is used for negative a, formula (25) for positive a.

This completes our study of ``binomial-coefficientology.''  The reader is advised
to learn especially Eqs. (5), (6), (7), (9), (13), (17), (20), and (21)---frame
them in black!

With all these methods at our disposal, we should be able to solve ``almost
any'' problem that comes along, in at least three different ways.  The following
examples illustrate the techniques.

When r is a positive integer, what is
the value of BLAH?

Formula (7) is useful for disposing of the outside 
k:
DISPLAY.

What is the value of
DISPLAY?

Now the problem is tougher; the summation index
k appears in six places!  First we apply Eq. (20), and we obtain
DISPLAY.
We can now breathe more easily, since several of the menacing characteristics
of the original formula have now disappeared. The next step should be obvious;
we apply Eq. (7) in a manner similar to the technique used in Problem 1:
DISPLAY,
and another k has disappeared.  There are now two equally promising lines of
attack.  We can replace
DISPLAY
and use Eq. (23):
DISPLAY.
Now
DISPLAY
equals zero except when BLAH, in which case it equals one.

It is convenient to represent the answer to our problem by using the
``Kronecker delta'' notation:
DISPLAY.
Using the BLAH-symbol, we have found that the answer is BLAH.

Another way to proceed from Eq. (27) is to use Eq. (17), obtaining
DISPLAY.
At this point Eq. (22) does not apply (since it requires that BLAH), but we
can use Eq. (6) so that Eq. (21) applies:
DISPLAY,
and once again we have derived the answer:
DISPLAY.

What is the value of
DISPLAY?

If m were zero, we would have the same formula
to work with that we had in Problem 2.  However, now the presence of m means
that we cannot even begin to use the method of the previous solution, since the
first step there was to use Eq. (20), which no longer applies.  In this situation
it pays to complicate things even more by replacing
DISPLAY
by a sum of terms of the form
DISPLAY,
since our problem then becomes a sum of problems we know how to solve!  Accordingly,
we use Eq. (25) with
DISPLAY,
and we have
DISPLAY.
We wish to perform the summation on k first; interchanging the order of summation
demands that we sum on the values of k which are BLAH and BLAH.  The latter
condition raises problems, because if BLAH, we do not know the desired
sum. Let us save the situation, however, by observing the terms of (30) are
zero when BLAH.  This condition implies that BLAH; thus 
BLAH, and the first binomial coefficient in (30) vanishes.
We may therefore replace the condition on the second sum by ``BLAH,'' and
the interchange of summation is done easily.  Summing on k by Eq. (29) now gives
DISPLAY,
and all terms vanish except BLAH; hence our final answer is
DISPLAY.

The solution to this problem was fairly complicated, but not really mysterious;
there was a good reason for each step.  The derivation should be studied closely
because it illustrates some delicate maneuvering with the conditions in our
equations.  There is actually a better way to attack this problem, however; it
is left to the reader to figure out a way to transform the given problem so that
Eq. (26) applies (see exercise 30).

Prove that
DISPLAY,
where BLAH is the nth degree polynomial in x which satisfies
DISPLAY.

We may assume that BLAH for BLAH, since
(31) is a polynomial in r, s, t.  Our problem is to evaluate
DISPLAY,
which, if anything, looks much worse than our previous horrible problems!  Note
the strong similarity to Eq. (26), however, and also note the case BLAH.

We are tempted to change
DISPLAY,
except that the latter tends to lose the analogy with Eq. (26) and it fails when
BLAH.  The best way to proceed is to use the technique of ``partial fractions,''
i.e., a complicated denominator can often be replaced by a sum of simpler
denominators.  Indeed, we have
DISPLAY.
Putting this into our sum we get
DISPLAY,
and Eq. (26) evaluates both of these if we change k to BLAH in the second
formula; the desired result follows immediately.  Identities (26) and (31) are
due to H. A. Rothe, Formulae de serierum reversione (Leipzig, 1793);
special cases of these formulas are still being ``discovered'' frequently.
For the interesting history of these identities and some generalizations, see
H. W. Gould and J. Kaucky, Journal of Combinatorial Theory 1
(1966), 233--248.

Determine the values of BLAH
such that
DISPLAY
for all nonnegative numbers.

This question came up in the previous section
(cf. Eq. 1.2.5--11) and we stated the answer without proof.  Let us pretend
we do not know the answer.  It is clear that the problem has a solution,
since we can set BLAH and determine BLAH,
etc.

First we would like to write Eq. (32) in terms of binomial coefficients:
DISPLAY.
The problem of solving implicit equations like this for BLAH is called the
inversion problem, and the technique to be used applies to similar
problems as well.

The idea is based on the following special case of Eq. (23) (BLAH):
DISPLAY.
The importance of this formula is that when BLAH, the sum is zero; this enables
us to solve our problem since a lot of terms cancel out as they did in Problem 3:
DISPLAY.
Note how we were able to get an equation in which only one value BLAH 
appears---by adding together suitable multiples of Eq. (33) for BLAH.
We have now
DISPLAY.

This completes the solution to Problem 5.  Let us now take a closer look at
the implications of Eq. (34): we have
DISPLAY,
since the first terms vanish after summation.
By properly choosing the coefficients
BLAH, we can represent any polynomial in k as a sum of binomial
coefficients with upper index k.  We threfore find that
DISPLAY,
where BLAH represents any polynomial whatever of degree r of
less.  [This formula will be of no great surprise to students of numerical 
analysis, since BLAH is the ``rth difference''
of the function BLAH.
Using Eq. (35), we can immediately obtain many other relations which appear
complicated at first and which are often given very lengthy proofs, e.g.,
DISPLAY.

It is customary in textbooks such as this to give a lot of impressive examples of
neat tricks, etc., but to never mention simple-looking problems where the techniques
fail.  The above examples may have given the impression that all things are 
possible with binomial coefficients; it should be mentioned however, that in
spite of Eqs. (10), (11), and (18), there seems to be no simple formula for the
analogous sum
DISPLAY,
when BLAH. (For BLAH the answer is simple; what is it?  See exercise 36.)

There are several generalizations of the concept of binomial coefficients, which
we will discuss briefly.  First, we can consider arbitrary real values of the
lower index k in BLAH; see exercises 40 through 45.  We also have the
generalization
DISPLAY,
which, as q approaches the limiting value one, becomes the ordinary binomial
coefficient BLAH.  [This can be seen by dividing each
term in numerator and denominator by BLAH.]  The basic properties of such
``q-nomial coefficients'' are discussed in exercise 58.

However, for our purposes the most important generalization is the 
multinomial coefficient
DISPLAY.
The principal property of multinomial coefficients is the generalization of
Eq. (13):
DISPLAY.
It is important to observe that any multinomial coefficient can be expressed in
terms of binomial coefficients:
DISPLAY,
so we may apply the techniques we already know for manipulating binomial
coefficients.  Note that (20) is a trinomial coefficient.

We conclude this section with a brief analysis of the transformation from a
polynomial expressed in powers of k to a polynomial expressed in binomial
coefficients.  The coefficients involved in this transformation are called
Stirling numbers, and these numbers will arise several times in later
sections of this book.

Stirling numbers come in two flavors: we denote Stirling numbers of the first
kind by BLAH, and those of the second kind by BLAH.
Table 2 displays ``Stirling's triangles,'' which are in some ways analogous
to Pascal's triangle.

There is absolutely no agreement today on notation for Stirling's numbers.  Some
authors define half of the Stirling numbers to be the negatives of the values
given here.  However, the notation used here, in which all Stirling numbers are
nonnegative, makes it much easier to remember the analogies with binomial
coefficients.

Stirling numbers of the first kind are used to convert from binomial coefficients
to powers:
DISPLAY.
For example, from Table 2,
DISPLAY.

Stirling numbers of the second kind are used to convert from powers to binomial
coefficients:
DISPLAY.
For example, from Table 2,

We shall now list the most important identities involving Stirling numbers.
(In these equations, the variables m and n always denote nonnegative integers.)

Some other fundamental Stirling number identities appear in exercises 1.2.6--61,
1.2.7--6, and in Eqs. (23), (26), (27), and (28) of Section 1.2.9.  For further
information on Stirling numbers, see Karoly (Charles) Jordan, Calculus of
Finite Differences (New York: Chelsea, 1947), Chapter 4.